//二叉堆他是一种特殊得二叉树 也就是堆数据结构 也叫做二叉堆 它能快速高效的找出最大值和最小值 常被用于 优先队列
//定义
/**
 * 它是一棵完全二叉树 表示树的每一层都有左侧和右侧子节点(除了最后一层的叶节点) 并且最后一层的叶节点尽可能都是左侧子节点 这叫做结构特性
 * 二叉堆不是最小堆就是最大堆 最小堆允许你快速的导出树的最小值 最大值,所有的节点都大于等于(最大堆)或小于等于(最小堆)每个 它的子节点被叫做堆特性
 */

/**
 * 最小堆的实现
 *      insert(val):向方法中插入一个新的值 如果插入成功 返回true 否则返回false
 *      extract():这个方法移除最小值(最小堆)或最大值(最大堆),并返回这个值
 *      findMinmun():这个方法返回最小值(最小堆)或最大值(最大堆)且不不会移除这个值 
 */

/**
 * 获取节点 使用一个数组 通过索引值检索父节点,左侧和右侧节点的值
 *      getLeftIndex(index):获取 他的左侧子节点位置 操作逻辑2* index+1
 *      getRightIndex(index):获取 他的右侧子节点位置 操作逻辑2*index+2
 *      getParentIndex(index):获取父节点位置:操作逻辑 index/2
 *      size():获取长度
 *      isEmpty():判断是为空
 */

const Compare = {
    LESS_THAN: -1,
    BIGGER_THAN: 1,
    EQUALS: 0
}
function defalutCompare (a, b) {
    if (a === b) {
        return Compare.EQUALS
    }
    return a < b ? Compare.LESS_THAN : Compare.BIGGER_THAN
}
function swap (array, a, b) {
    [array[a], array[b]] = [array[b], array[a]]
}
class MinHeap {
    constructor () {
        this.compareFn = defalutCompare
        this.heap = []
    }
    //获取左节点的位置
    getLeftIndex (index) {
        return (2 * index) + 1
    }
    //获取右节点的位置
    getRigthIndex (index) {
        return (2 * index) + 2
    }
    // 获取父节点的位置
    getParentIndex (index) {
        if (index === 0) {
            return undefined
        }
        return Math.floor((index - 1) / 2)
    }
    // 获取堆长度
    size () {
        return this.heap.length
    }
    //判断堆是否为空
    isEmpty () {
        return this.size() <= 0
    }
    clear () {
        this.heap = []
    }
    findMinmun () {
        return this.isEmpty() ? undefined : this.heap[0]
    }
    insert (value) {
        if (value !== null) {
            const index = this.heap.length
            this.heap.push(value)
            this.siftUp(index)
            return true
        }
        return false
    }
    siftDown (index) {
        let element = index
        const left = this.getLeftIndex(index)  //获取左侧子节点
        const right = this.getRigthIndex(index) //获取右侧子节点
        const size = this.size()
        if (left < size && this.compareFn(this.heap[element], this.heap[left] === Compare.BIGGER_THAN)) {
            element = left
        }
    }
}